Ploidy Review

求断点
预处理断点数据
求极值

断点

$V_{i} i \in [0, n]$
$⌊ ρ V_{i} + 0.5 ⌋ = z, z \in Z$
$ρ = \frac{n - 0.5}{V_{i}}$

$(ρ V_{0} - ⌊ ρ V_{0} + 0.5 ⌋)^{2} + (ρ V_{1} - ⌊ ρ V_{1} + 0.5 ⌋)^{2} + . . . + (ρ V_{i} - ⌊ ρ V_{i} + 0.5 ⌋)^{2}$

预处理断点数据

对每个断点算出所有的 $⌊ ρ V_{i} + 0.5 ⌋$
$∵ V_{i}$ 已知 $∴$ 给定 $ρ$ 的每一组 $⌊ ρ V_{i} + 0.5 ⌋$ 可求

求极值

$l e t k_{i} = ⌊ ρ V_{i} + 0.5 ⌋ i \in [0, n]$

$(ρ V_{0} - ⌊ ρ V_{0} + 0.5 ⌋)^{2} + (ρ V_{1} - ⌊ ρ V_{1} + 0.5 ⌋)^{2} + . . . + (ρ V_{i} - ⌊ ρ V_{i} + 0.5 ⌋)^{2}$

$= (ρ V_{0} - k_{0})^{2} + (ρ V_{1} - k_{1})^{2} + . . . + (ρ V_{i} - k_{i})^{2}$

$= (ρ^{2} V_{0}^{2} - 2 ρ k_{0} V_{0} + k_{0}^{2}) + (ρ^{2} V_{1}^{2} - 2 ρ k_{0} V_{1} + k_{1}^{2}) + \dots + (ρ^{2} V_{i}^{2} - 2 ρ k_{i} V_{i} + k_{i}^{2})$

$= ρ^{2} (V_{0}^{2} + V_{1}^{2} + \dots + V_{i}^{2}) - 2 ρ (k_{0} V_{0} + k_{1} V_{1} + \dots + k_{i} V_{i}) + (k_{0}^{2} + k_{1}^{2} + \dots + k_{i}^{2})$

$= ρ^{2} \sum_{i = 0}^{n} V_{i}^{2} - 2 ρ \sum_{i = 0}^{n} k_{i} V_{i} + \sum_{i = 0}^{n} k_{i}^{2}$

$l e t K = \sum_{i = 0}^{n} k_{i}^{2}, V = \sum_{i = 0}^{n} V_{i}^{2} i \in [0, n]$

$= ρ^{2} V - 2 ρ \sum_{i = 0}^{n} k_{i} V_{i} + K$

Algorithm

Tutorial

assignment

Assignment

As-1

As-2

Lab-1

Lab-2

Lab-3

Lab-4

GAMES101

Assignment-1

Assignment-2

Assignment-3

Assignment-4

Lab

Lecture

Peoject

CSCN

Ploidy

Ploidy Review ​

断点 ​

预处理断点数据 ​

求极值 ​

Ploidy Review

断点

预处理断点数据

求极值